<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Tutorial</title>
<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
<link rel="up" href="../poly_collection.html" title="Chapter 29. Boost.PolyCollection">
<link rel="prev" href="an_efficient_polymorphic_data_st.html" title="An efficient polymorphic data structure">
<link rel="next" href="performance.html" title="Performance">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td>
<td align="center"><a href="../../../index.html">Home</a></td>
<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="an_efficient_polymorphic_data_st.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../poly_collection.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="performance.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="poly_collection.tutorial"></a><a class="link" href="tutorial.html" title="Tutorial">Tutorial</a>
</h2></div></div></div>
<div class="toc"><dl class="toc">
<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.basics">Basics</a></span></dt>
<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature">Deeper
      into the segmented nature of Boost.PolyCollection</a></span></dt>
<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.insertion_and_emplacement">Insertion
      and emplacement</a></span></dt>
<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.exceptions">Exceptions</a></span></dt>
<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.algorithms">Algorithms</a></span></dt>
</dl></div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="poly_collection.tutorial.basics"></a><a class="link" href="tutorial.html#poly_collection.tutorial.basics" title="Basics">Basics</a>
</h3></div></div></div>
<div class="toc"><dl class="toc">
<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.basics.boost_base_collection"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span></code></a></span></dt>
<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.basics.boost_function_collection"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span></code></a></span></dt>
<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.basics.boost_any_collection"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span></code></a></span></dt>
</dl></div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="poly_collection.tutorial.basics.boost_base_collection"></a><a class="link" href="tutorial.html#poly_collection.tutorial.basics.boost_base_collection" title="boost::base_collection"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span></code></a>
</h4></div></div></div>
<p>
          (Code samples from <a href="../../../libs/poly_collection/example/basic_base.cpp" target="_top"><code class="computeroutput"><span class="identifier">basic_base</span><span class="special">.</span><span class="identifier">cpp</span></code></a>.)
        </p>
<p>
          Imagine we are developing a role playing game in C++ where sprites are
          rendered on screen; for the purposes of illustration we can model rendering
          simply as outputting some information to a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span></code>:
        </p>
<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">sprite</span>
<span class="special">{</span>
  <span class="identifier">sprite</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">id</span><span class="special">):</span><span class="identifier">id</span><span class="special">{</span><span class="identifier">id</span><span class="special">}{}</span>
  <span class="keyword">virtual</span> <span class="special">~</span><span class="identifier">sprite</span><span class="special">()=</span><span class="keyword">default</span><span class="special">;</span>
  <span class="keyword">virtual</span> <span class="keyword">void</span> <span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="identifier">os</span><span class="special">)</span><span class="keyword">const</span><span class="special">=</span><span class="number">0</span><span class="special">;</span>

  <span class="keyword">int</span> <span class="identifier">id</span><span class="special">;</span>
<span class="special">};</span>
</pre>
<p>
          The game features warriors, juggernauts (a special type of warrior) and
          goblins, each represented by its own class derived (directly or indirectly)
          from <code class="computeroutput"><span class="identifier">sprite</span></code>:
        </p>
<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">warrior</span><span class="special">:</span><span class="identifier">sprite</span>
<span class="special">{</span>
  <span class="keyword">using</span> <span class="identifier">sprite</span><span class="special">::</span><span class="identifier">sprite</span><span class="special">;</span>
  <span class="identifier">warrior</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="identifier">rank</span><span class="special">,</span><span class="keyword">int</span> <span class="identifier">id</span><span class="special">):</span><span class="identifier">sprite</span><span class="special">{</span><span class="identifier">id</span><span class="special">},</span><span class="identifier">rank</span><span class="special">{</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">move</span><span class="special">(</span><span class="identifier">rank</span><span class="special">)}{}</span>

  <span class="keyword">void</span> <span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="identifier">os</span><span class="special">)</span><span class="keyword">const</span> <span class="identifier">override</span><span class="special">{</span><span class="identifier">os</span><span class="special">&lt;&lt;</span><span class="identifier">rank</span><span class="special">&lt;&lt;</span><span class="string">" "</span><span class="special">&lt;&lt;</span><span class="identifier">id</span><span class="special">;}</span>

  <span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="identifier">rank</span><span class="special">=</span><span class="string">"warrior"</span><span class="special">;</span>
<span class="special">};</span>

<span class="keyword">struct</span> <span class="identifier">juggernaut</span><span class="special">:</span><span class="identifier">warrior</span>
<span class="special">{</span>
  <span class="identifier">juggernaut</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">id</span><span class="special">):</span><span class="identifier">warrior</span><span class="special">{</span><span class="string">"juggernaut"</span><span class="special">,</span><span class="identifier">id</span><span class="special">}{}</span>
<span class="special">};</span>

<span class="keyword">struct</span> <span class="identifier">goblin</span><span class="special">:</span><span class="identifier">sprite</span>
<span class="special">{</span>
  <span class="keyword">using</span> <span class="identifier">sprite</span><span class="special">::</span><span class="identifier">sprite</span><span class="special">;</span>
  <span class="keyword">void</span> <span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="identifier">os</span><span class="special">)</span><span class="keyword">const</span> <span class="identifier">override</span><span class="special">{</span><span class="identifier">os</span><span class="special">&lt;&lt;</span><span class="string">"goblin "</span><span class="special">&lt;&lt;</span><span class="identifier">id</span><span class="special">;}</span>
<span class="special">};</span>
</pre>
<p>
          Let us populate a polymorphic collection with an assortment of sprites:
        </p>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">poly_collection</span><span class="special">/</span><span class="identifier">base_collection</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
<span class="special">...</span>

<span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span><span class="special">&lt;</span><span class="identifier">sprite</span><span class="special">&gt;</span> <span class="identifier">c</span><span class="special">;</span>

<span class="identifier">std</span><span class="special">::</span><span class="identifier">mt19937</span>                 <span class="identifier">gen</span><span class="special">{</span><span class="number">92748</span><span class="special">};</span> <span class="comment">// some arbitrary random seed</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">discrete_distribution</span><span class="special">&lt;&gt;</span> <span class="identifier">rnd</span><span class="special">{{</span><span class="number">1</span><span class="special">,</span><span class="number">1</span><span class="special">,</span><span class="number">1</span><span class="special">}};</span>
<span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">=</span><span class="number">0</span><span class="special">;</span><span class="identifier">i</span><span class="special">&lt;</span><span class="number">8</span><span class="special">;++</span><span class="identifier">i</span><span class="special">){</span>        <span class="comment">// assign each type with 1/3 probability</span>
  <span class="keyword">switch</span><span class="special">(</span><span class="identifier">rnd</span><span class="special">(</span><span class="identifier">gen</span><span class="special">)){</span>
    <span class="keyword">case</span> <span class="number">0</span><span class="special">:</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">warrior</span><span class="special">{</span><span class="identifier">i</span><span class="special">});</span><span class="keyword">break</span><span class="special">;</span>
    <span class="keyword">case</span> <span class="number">1</span><span class="special">:</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">juggernaut</span><span class="special">{</span><span class="identifier">i</span><span class="special">});</span><span class="keyword">break</span><span class="special">;</span>
    <span class="keyword">case</span> <span class="number">2</span><span class="special">:</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">goblin</span><span class="special">{</span><span class="identifier">i</span><span class="special">});</span><span class="keyword">break</span><span class="special">;</span>
  <span class="special">}</span>
<span class="special">}</span>
</pre>
<p>
          There are two aspects to notice here:
        </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
              <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span></code> does not have a
              <code class="computeroutput"><span class="identifier">push_back</span></code> member function
              like, say, <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span></code>, as the order in which elements
              are stored cannot be freely chosen by the user code —we will
              see more about this later. The insertion mechanisms are rather those
              of containers like <a href="http://en.cppreference.com/w/cpp/container/unordered_multiset" target="_top"><code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">unordered_multiset</span></code></a>, namely
              <code class="computeroutput"><span class="identifier">insert</span></code> and <code class="computeroutput"><span class="identifier">emplace</span></code> with or without a position
              <span class="emphasis"><em>hint</em></span>.
            </li>
<li class="listitem">
              Elements are not created with <code class="computeroutput"><span class="keyword">new</span></code>
              but constructed on the stack and passed directly much like one would
              do with a standard non-polymorphic container.
            </li>
</ul></div>
<div class="important"><table border="0" summary="Important">
<tr>
<td rowspan="2" align="center" valign="top" width="25"><img alt="[Important]" src="../../../doc/src/images/important.png"></td>
<th align="left">Important</th>
</tr>
<tr><td align="left" valign="top"><p>
            Elements inserted into a <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span></code>
            (or the other containers of Boost.PolyCollection) must be copyable and
            assignable; strictly speaking, they must at least model <a href="http://en.cppreference.com/w/cpp/named_req/MoveConstructible" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">MoveConstructible</span></code></strong></span></a>
            and either be <a href="http://en.cppreference.com/w/cpp/named_req/MoveAssignable" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">MoveAssignable</span></code></strong></span></a>
            or not throw on move construction. This might force you to revisit your
            code as it is customary to explicitly forbid copying at the base level
            of a virtual hierarchy to avoid <a href="https://en.wikipedia.org/wiki/Object_slicing" target="_top"><span class="emphasis"><em>slicing</em></span></a>.
          </p></td></tr>
</table></div>
<p>
          Rendering can now be implemented with a simple <code class="computeroutput"><span class="keyword">for</span></code>
          loop over <code class="computeroutput"><span class="identifier">c</span></code>:
        </p>
<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span>
<span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&amp;</span> <span class="identifier">s</span><span class="special">:</span><span class="identifier">c</span><span class="special">){</span>
  <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
  <span class="identifier">s</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span>
  <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
<span class="special">}</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
</pre>
<p>
          The output being:
        </p>
<pre class="programlisting">juggernaut 0,juggernaut 4,juggernaut 7,goblin 1,goblin 3,goblin 5,warrior 2,warrior 6
</pre>
<p>
          As we have forewarned, the traversal order does not correspond to that
          of insertion. Instead, the elements are grouped in <span class="emphasis"><em>segments</em></span>
          according to their concrete type. Here we see that juggernauts come first,
          followed by goblins and warriors. In general, no assumptions should be
          made about segment ordering, which may be different for this very example
          in your environment. On the other hand, elements inserted into an already
          existing segment always come at the end (except if a hint is provided).
          For instance, after inserting a latecomer goblin with <code class="computeroutput"><span class="identifier">id</span><span class="special">==</span><span class="number">8</span></code>:
        </p>
<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">goblin</span><span class="special">{</span><span class="number">8</span><span class="special">});</span>
</pre>
<p>
          the rendering loop outputs (new element in red):
        </p>
<pre class="programlisting">juggernaut 0,juggernaut 4,juggernaut 7,goblin 1,goblin 3,goblin 5,<span class="red">goblin 8</span>,warrior 2,warrior 6
</pre>
<p>
          Deletion can be done in the usual way:
        </p>
<pre class="programlisting"><span class="comment">// find element with id==7 and remove it</span>
<span class="keyword">auto</span> <span class="identifier">it</span><span class="special">=</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">find_if</span><span class="special">(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),[](</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&amp;</span> <span class="identifier">s</span><span class="special">){</span><span class="keyword">return</span> <span class="identifier">s</span><span class="special">.</span><span class="identifier">id</span><span class="special">==</span><span class="number">7</span><span class="special">;});</span>
<span class="identifier">c</span><span class="special">.</span><span class="identifier">erase</span><span class="special">(</span><span class="identifier">it</span><span class="special">);</span>
</pre>
<p>
          Now rendering emits:
        </p>
<pre class="programlisting">juggernaut 0,juggernaut 4,goblin 1,goblin 3,goblin 5,goblin 8,warrior 2,warrior 6
</pre>
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="poly_collection.tutorial.basics.boost_function_collection"></a><a class="link" href="tutorial.html#poly_collection.tutorial.basics.boost_function_collection" title="boost::function_collection"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span></code></a>
</h4></div></div></div>
<p>
          (Code samples from <a href="../../../libs/poly_collection/example/basic_function.cpp" target="_top"><code class="computeroutput"><span class="identifier">basic_function</span><span class="special">.</span><span class="identifier">cpp</span></code></a>. C++14 <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">make_unique</span></code>
          is used.)
        </p>
<p>
          Well into the development of the game, the product manager requests that
          two new types of entities be added to the rendering loop:
        </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
              Overlaid messages, such as scores, modelled as <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span></code>s.
            </li>
<li class="listitem">
              Pop-up windows coming from a third party library that, unfortunately,
              do not derive from <code class="computeroutput"><span class="identifier">sprite</span></code>
              and use their own <code class="computeroutput"><span class="identifier">display</span></code>
              member functon for rendering:
            </li>
</ul></div>
<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">window</span>
<span class="special">{</span>
  <span class="identifier">window</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="identifier">caption</span><span class="special">):</span><span class="identifier">caption</span><span class="special">{</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">move</span><span class="special">(</span><span class="identifier">caption</span><span class="special">)}{}</span>

  <span class="keyword">void</span> <span class="identifier">display</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="identifier">os</span><span class="special">)</span><span class="keyword">const</span><span class="special">{</span><span class="identifier">os</span><span class="special">&lt;&lt;</span><span class="string">"["</span><span class="special">&lt;&lt;</span><span class="identifier">caption</span><span class="special">&lt;&lt;</span><span class="string">"]"</span><span class="special">;}</span>

  <span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="identifier">caption</span><span class="special">;</span>
<span class="special">};</span>
</pre>
<p>
          We then decide to refactor the code so that sprites, messsages and windows
          are stored in dedicated containers:
        </p>
<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">unique_ptr</span><span class="special">&lt;</span><span class="identifier">sprite</span><span class="special">&gt;&gt;</span> <span class="identifier">sprs</span><span class="special">;</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">&gt;</span>             <span class="identifier">msgs</span><span class="special">;</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">window</span><span class="special">&gt;</span>                  <span class="identifier">wnds</span><span class="special">;</span>
</pre>
<p>
          and define our rendering container as a <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span></code>
          of <span class="emphasis"><em>callable entities</em></span> —function pointers or
          objects with a function call <code class="computeroutput"><span class="keyword">operator</span><span class="special">()</span></code>— accepting a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span></code> as a parameter
        </p>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">poly_collection</span><span class="special">/</span><span class="identifier">function_collection</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
<span class="special">...</span>

<span class="comment">// function signature accepting std::ostream&amp; and returning nothing</span>
<span class="keyword">using</span> <span class="identifier">render_callback</span><span class="special">=</span><span class="keyword">void</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;);</span>

<span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span><span class="special">&lt;</span><span class="identifier">render_callback</span><span class="special">&gt;</span> <span class="identifier">c</span><span class="special">;</span>
</pre>
<p>
          which we fill with suitable adaptors for <code class="computeroutput"><span class="identifier">sprite</span></code>s,
          <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span></code>s and <code class="computeroutput"><span class="identifier">window</span></code>s,
          respectively. Lambda functions allow for a particularly terse code.
        </p>
<pre class="programlisting"><span class="keyword">auto</span> <span class="identifier">render_sprite</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&amp;</span> <span class="identifier">s</span><span class="special">){</span>
  <span class="keyword">return</span> <span class="special">[&amp;](</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="identifier">os</span><span class="special">){</span><span class="identifier">s</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">os</span><span class="special">);};</span>
<span class="special">}</span>

<span class="keyword">auto</span> <span class="identifier">render_message</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">&amp;</span> <span class="identifier">m</span><span class="special">){</span>
  <span class="keyword">return</span> <span class="special">[&amp;](</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="identifier">os</span><span class="special">){</span><span class="identifier">os</span><span class="special">&lt;&lt;</span><span class="identifier">m</span><span class="special">;};</span>
<span class="special">}</span>

<span class="keyword">auto</span> <span class="identifier">render_window</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">window</span><span class="special">&amp;</span> <span class="identifier">w</span><span class="special">){</span>
  <span class="keyword">return</span> <span class="special">[&amp;](</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="identifier">os</span><span class="special">){</span><span class="identifier">w</span><span class="special">.</span><span class="identifier">display</span><span class="special">(</span><span class="identifier">os</span><span class="special">);};</span>
<span class="special">}</span>
<span class="special">...</span>

<span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&amp;</span> <span class="identifier">ps</span><span class="special">:</span><span class="identifier">sprs</span><span class="special">)</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">render_sprite</span><span class="special">(*</span><span class="identifier">ps</span><span class="special">));</span>
<span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&amp;</span> <span class="identifier">m</span><span class="special">:</span><span class="identifier">msgs</span><span class="special">)</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">render_message</span><span class="special">(</span><span class="identifier">m</span><span class="special">));</span>
<span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&amp;</span> <span class="identifier">w</span><span class="special">:</span><span class="identifier">wnds</span><span class="special">)</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">render_window</span><span class="special">(</span><span class="identifier">w</span><span class="special">));</span>
</pre>
<p>
          The rendering loop now looks like this:
        </p>
<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span>
<span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&amp;</span> <span class="identifier">cbk</span><span class="special">:</span><span class="identifier">c</span><span class="special">){</span>
  <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
  <span class="identifier">cbk</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span>
  <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
<span class="special">}</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
</pre>
<p>
          and produces the following for a particular scenario of sprites, messages
          and windows:
        </p>
<pre class="programlisting">juggernaut 0,goblin 1,warrior 2,goblin 3,"stamina: 10,000","game over",[pop-up 1],[pop-up 2]
</pre>
<p>
          The container we have just created works in many respects like a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">function</span><span class="special">&lt;</span><span class="identifier">render_callback</span><span class="special">&gt;&gt;</span></code>,
          the main difference being that with <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span></code>
          callable entities of the same type are packed together in memory <a href="#ftn.poly_collection.tutorial.basics.boost_function_collection.f0" class="footnote" name="poly_collection.tutorial.basics.boost_function_collection.f0"><sup class="footnote">[12]</sup></a>, thus increasing performance (which is the whole point of using
          Boost.PolyCollection), while a vector of <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">function</span></code>s
          results in an individual allocation for each entity stored <a href="#ftn.poly_collection.tutorial.basics.boost_function_collection.f1" class="footnote" name="poly_collection.tutorial.basics.boost_function_collection.f1"><sup class="footnote">[13]</sup></a>. In fact, the <code class="computeroutput"><span class="identifier">value_type</span></code>
          elements held by a <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span></code>
          are actually <span class="emphasis"><em>not</em></span> <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">function</span></code>s,
          although they behave analogously and can be converted to <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">function</span></code> if needed:
        </p>
<pre class="programlisting"><span class="keyword">auto</span> <span class="identifier">cbk</span><span class="special">=*</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">();</span>
<span class="identifier">cbk</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span> <span class="comment">// renders first element to std::cout</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">function</span><span class="special">&lt;</span><span class="identifier">render_callback</span><span class="special">&gt;</span> <span class="identifier">f</span><span class="special">=</span><span class="identifier">cbk</span><span class="special">;</span>
<span class="identifier">f</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span>   <span class="comment">// exactly the same</span>
</pre>
<p>
          There is a reason for this: elements of a polymorphic collection cannot
          be freely assigned to by the user as this could end up trying to insert
          an object into a segment of a different type. So, unlike with <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">function</span></code>, this will not work:
        </p>
<pre class="programlisting"><span class="special">*</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()=</span><span class="identifier">render_message</span><span class="special">(</span><span class="string">"last minute message"</span><span class="special">);</span> <span class="comment">// compile-time error</span>
</pre>
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="poly_collection.tutorial.basics.boost_any_collection"></a><a class="link" href="tutorial.html#poly_collection.tutorial.basics.boost_any_collection" title="boost::any_collection"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span></code></a>
</h4></div></div></div>
<p>
          (Code samples from <a href="../../../libs/poly_collection/example/basic_any.cpp" target="_top"><code class="computeroutput"><span class="identifier">basic_any</span><span class="special">.</span><span class="identifier">cpp</span></code></a>.)
        </p>
<div class="note"><table border="0" summary="Note">
<tr>
<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../doc/src/images/note.png"></td>
<th align="left">Note</th>
</tr>
<tr><td align="left" valign="top"><p>
            Here we just touch on the bare essentials of <a href="../../../libs/type_erasure" target="_top">Boost.TypeErasure</a>
            needed to present <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span></code>.
            The reader is advised to read Boost.TypeErasure documentation for further
            information.
          </p></td></tr>
</table></div>
<p>
          After measuring the performance of the latest changes, we find that rendering
          is too slow and decide to refactor once again: if we could store all the
          entities --sprites, messages and windows-- into one single container, that
          would eliminate a level of indirection. The problem is that these types
          are totally unrelated to each other.
        </p>
<p>
          <a href="../../../libs/type_erasure" target="_top">Boost.TypeErasure</a> provides
          a class template <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">any</span><span class="special">&lt;</span><span class="identifier">Concept</span><span class="special">&gt;</span></code> able to hold an object of whatever
          type as long as it conforms to the interface specified by <code class="computeroutput"><span class="identifier">Concept</span></code>. In our case, we find it particularly
          easy to implement a common interface for rendering by providing overloads
          of <code class="computeroutput"><span class="keyword">operator</span><span class="special">&lt;&lt;</span></code>
        </p>
<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="keyword">operator</span><span class="special">&lt;&lt;(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="identifier">os</span><span class="special">,</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&amp;</span> <span class="identifier">s</span><span class="special">)</span>
<span class="special">{</span>
  <span class="identifier">s</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">os</span><span class="special">);</span>
  <span class="keyword">return</span> <span class="identifier">os</span><span class="special">;</span>
<span class="special">}</span>

<span class="comment">// std::string already has a suitable operator&lt;&lt;</span>

<span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="keyword">operator</span><span class="special">&lt;&lt;(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="identifier">os</span><span class="special">,</span><span class="keyword">const</span> <span class="identifier">window</span><span class="special">&amp;</span> <span class="identifier">w</span><span class="special">)</span>
<span class="special">{</span>
  <span class="identifier">w</span><span class="special">.</span><span class="identifier">display</span><span class="special">(</span><span class="identifier">os</span><span class="special">);</span>
  <span class="keyword">return</span> <span class="identifier">os</span><span class="special">;</span>
<span class="special">}</span>
</pre>
<p>
          so that we can use it to specify the interface all entities have to adhere
          to:
        </p>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">poly_collection</span><span class="special">/</span><span class="identifier">any_collection</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
<span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">type_erasure</span><span class="special">/</span><span class="identifier">operators</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
<span class="special">...</span>

<span class="keyword">using</span> <span class="identifier">renderable</span><span class="special">=</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">ostreamable</span><span class="special">&lt;&gt;;</span>
<span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span><span class="special">&lt;</span><span class="identifier">renderable</span><span class="special">&gt;</span> <span class="identifier">c</span><span class="special">;</span>
</pre>
<p>
          The collection just created happily accepts insertion of heterogeneous
          entities (since interface conformity is silently checked at compile time)
        </p>
<pre class="programlisting"><span class="comment">// populate with sprites</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">mt19937</span>                 <span class="identifier">gen</span><span class="special">{</span><span class="number">92748</span><span class="special">};</span> <span class="comment">// some arbitrary random seed</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">discrete_distribution</span><span class="special">&lt;&gt;</span> <span class="identifier">rnd</span><span class="special">{{</span><span class="number">1</span><span class="special">,</span><span class="number">1</span><span class="special">,</span><span class="number">1</span><span class="special">}};</span>
<span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">=</span><span class="number">0</span><span class="special">;</span><span class="identifier">i</span><span class="special">&lt;</span><span class="number">4</span><span class="special">;++</span><span class="identifier">i</span><span class="special">){</span>        <span class="comment">// assign each type with 1/3 probability</span>
  <span class="keyword">switch</span><span class="special">(</span><span class="identifier">rnd</span><span class="special">(</span><span class="identifier">gen</span><span class="special">)){</span>
    <span class="keyword">case</span> <span class="number">0</span><span class="special">:</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">warrior</span><span class="special">{</span><span class="identifier">i</span><span class="special">});</span><span class="keyword">break</span><span class="special">;</span>
    <span class="keyword">case</span> <span class="number">1</span><span class="special">:</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">juggernaut</span><span class="special">{</span><span class="identifier">i</span><span class="special">});</span><span class="keyword">break</span><span class="special">;</span>
    <span class="keyword">case</span> <span class="number">2</span><span class="special">:</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">goblin</span><span class="special">{</span><span class="identifier">i</span><span class="special">});</span><span class="keyword">break</span><span class="special">;</span>
  <span class="special">}</span>
<span class="special">}</span>

<span class="comment">// populate with messages</span>
<span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">{</span><span class="string">"\"stamina: 10,000\""</span><span class="special">});</span>
<span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">{</span><span class="string">"\"game over\""</span><span class="special">});</span>

<span class="comment">// populate with windows</span>
<span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">window</span><span class="special">{</span><span class="string">"pop-up 1"</span><span class="special">});</span>
<span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">window</span><span class="special">{</span><span class="string">"pop-up 2"</span><span class="special">});</span>
</pre>
<p>
          and rendering becomes
        </p>
<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span>
<span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&amp;</span> <span class="identifier">r</span><span class="special">:</span><span class="identifier">c</span><span class="special">){</span>
  <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">&lt;&lt;</span><span class="identifier">r</span><span class="special">;</span>
  <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
<span class="special">}</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
</pre>
<p>
          with output
        </p>
<pre class="programlisting">[pop-up 1],[pop-up 2],juggernaut 0,goblin 1,goblin 3,warrior 2,"stamina: 10,000","game over"
</pre>
<p>
          As was the case with <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span></code>,
          this container is similar to a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">any</span><span class="special">&lt;</span><span class="identifier">Concept</span><span class="special">&gt;&gt;</span></code> but has better performance due
          to packing of same-type elements. Also, the <code class="computeroutput"><span class="identifier">value_type</span></code>
          of a <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span><span class="special">&lt;</span><span class="identifier">Concept</span><span class="special">&gt;</span></code>
          is <span class="emphasis"><em>not</em></span> <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">any</span><span class="special">&lt;</span><span class="identifier">Concept</span><span class="special">&gt;</span></code>, but a similarly behaving entity <a href="#ftn.poly_collection.tutorial.basics.boost_any_collection.f0" class="footnote" name="poly_collection.tutorial.basics.boost_any_collection.f0"><sup class="footnote">[14]</sup></a>. In any case, we are not accessing sprites through an abstract
          <code class="computeroutput"><span class="identifier">sprite</span><span class="special">&amp;</span></code>
          anymore, so we could as well dismantle the virtual hierarchy and implement
          each type autonomously: this is left as an exercise to the reader.
        </p>
</div>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="poly_collection.tutorial.deeper_into_the_segmented_nature"></a><a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature" title="Deeper into the segmented nature of Boost.PolyCollection">Deeper
      into the segmented nature of Boost.PolyCollection</a>
</h3></div></div></div>
<div class="toc"><dl class="toc">
<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration">Type
        registration</a></span></dt>
<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.segment_specific_interface">Segment-specific
        interface</a></span></dt>
<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.local_iterators">Local
        iterators</a></span></dt>
<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.reserve">Reserve</a></span></dt>
</dl></div>
<p>
        (Code samples from <a href="../../../libs/poly_collection/example/segmented_structure.cpp" target="_top"><code class="computeroutput"><span class="identifier">segmented_structure</span><span class="special">.</span><span class="identifier">cpp</span></code></a>. C++14 <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">make_unique</span></code>
        is used.)
      </p>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration"></a><a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration" title="Type registration">Type
        registration</a>
</h4></div></div></div>
<p>
          Getting back to our <a class="link" href="tutorial.html#poly_collection.tutorial.basics.boost_base_collection" title="boost::base_collection"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span></code></a> example, suppose
          we want to refactor the populating code as follows:
        </p>
<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">unique_ptr</span><span class="special">&lt;</span><span class="identifier">sprite</span><span class="special">&gt;</span> <span class="identifier">make_sprite</span><span class="special">()</span>
<span class="special">{</span>
  <span class="keyword">static</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">mt19937</span>                 <span class="identifier">gen</span><span class="special">{</span><span class="number">92748</span><span class="special">};</span>
  <span class="keyword">static</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">discrete_distribution</span><span class="special">&lt;&gt;</span> <span class="identifier">rnd</span><span class="special">{{</span><span class="number">1</span><span class="special">,</span><span class="number">1</span><span class="special">,</span><span class="number">1</span><span class="special">}};</span>
  <span class="keyword">static</span> <span class="keyword">int</span>                          <span class="identifier">id</span><span class="special">=</span><span class="number">0</span><span class="special">;</span>

  <span class="keyword">switch</span><span class="special">(</span><span class="identifier">rnd</span><span class="special">(</span><span class="identifier">gen</span><span class="special">)){</span>
    <span class="keyword">case</span> <span class="number">0</span><span class="special">:</span> <span class="keyword">return</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">make_unique</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">&gt;(</span><span class="identifier">id</span><span class="special">++);</span><span class="keyword">break</span><span class="special">;</span>
    <span class="keyword">case</span> <span class="number">1</span><span class="special">:</span> <span class="keyword">return</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">make_unique</span><span class="special">&lt;</span><span class="identifier">juggernaut</span><span class="special">&gt;(</span><span class="identifier">id</span><span class="special">++);</span><span class="keyword">break</span><span class="special">;</span>
    <span class="keyword">case</span> <span class="number">2</span><span class="special">:</span> <span class="keyword">return</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">make_unique</span><span class="special">&lt;</span><span class="identifier">goblin</span><span class="special">&gt;(</span><span class="identifier">id</span><span class="special">++);</span><span class="keyword">break</span><span class="special">;</span>
  <span class="special">}</span>
<span class="special">}</span>
<span class="special">...</span>

<span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">=</span><span class="number">0</span><span class="special">;</span><span class="identifier">i</span><span class="special">&lt;</span><span class="number">8</span><span class="special">;++</span><span class="identifier">i</span><span class="special">)</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(*</span><span class="identifier">make_sprite</span><span class="special">());</span>
<span class="comment">// throws boost::poly_collection::unregistered_type</span>
</pre>
<p>
          Unexpectedly, this piece of code throws an exception of type <a class="link" href="reference.html#poly_collection.reference.header_boost_poly_collection_exc.class_unregistered_type" title="Class unregistered_type"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">unregistered_type</span></code></a>. What has changed
          from our original code?
        </p>
<p>
          Suppose a <code class="computeroutput"><span class="identifier">warrior</span></code> has been
          created by <code class="computeroutput"><span class="identifier">make_sprite</span></code>.
          The statement <code class="computeroutput"><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(*</span><span class="identifier">make_sprite</span><span class="special">())</span></code>
          is passing the object as a <code class="computeroutput"><span class="identifier">sprite</span><span class="special">&amp;</span></code>: even though <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span></code>
          is smart enough to know that the object is actually derived from <code class="computeroutput"><span class="identifier">sprite</span></code> (by using <a href="http://en.cppreference.com/w/cpp/language/typeid" target="_top"><code class="computeroutput"><span class="keyword">typeid</span><span class="special">()</span></code></a>)
          and <a href="https://en.wikipedia.org/wiki/Object_slicing" target="_top">slicing</a>
          is to be avoided, there is no way that a segment for it can be created
          without accessing the type <code class="computeroutput"><span class="identifier">warrior</span></code>
          <span class="emphasis"><em>at compile time</em></span> for the proper internal class templates
          to be instantiated <a href="#ftn.poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration.f0" class="footnote" name="poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration.f0"><sup class="footnote">[15]</sup></a>. This did not happen in the pre-refactoring code because objects
          were passed as references to their true types.
        </p>
<p>
          A type is said to be <span class="emphasis"><em>registered</em></span> into a polymorphic
          collection if there is a (potentially empty) segment created for it. This
          can be checked with:
        </p>
<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">is_registered</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">&gt;()&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>       <span class="comment">// prints 0</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">is_registered</span><span class="special">(</span><span class="keyword">typeid</span><span class="special">(</span><span class="identifier">warrior</span><span class="special">))&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span> <span class="comment">// alternate syntax</span>
</pre>
<p>
          Registration happens automatically when the object is passed as a reference
          to its true type or <a class="link" href="tutorial.html#poly_collection.tutorial.insertion_and_emplacement.emplacement"><code class="computeroutput"><span class="identifier">emplace</span></code></a>'d, and explicitly with
          <code class="computeroutput"><span class="identifier">register_types</span></code>:
        </p>
<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">register_types</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">,</span><span class="identifier">juggernaut</span><span class="special">,</span><span class="identifier">goblin</span><span class="special">&gt;();</span>
<span class="comment">// everything works fine now</span>
<span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">=</span><span class="number">0</span><span class="special">;</span><span class="identifier">i</span><span class="special">&lt;</span><span class="number">8</span><span class="special">;++</span><span class="identifier">i</span><span class="special">)</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(*</span><span class="identifier">make_sprite</span><span class="special">());</span>
</pre>
<p>
          Once <code class="computeroutput"><span class="identifier">T</span></code> has been registered
          into a polymorphic collection, it remains so regardless of whether objects
          of type <code class="computeroutput"><span class="identifier">T</span></code> are stored or
          not, except if the collection is moved from, assigned to, or swapped.
        </p>
<p>
          As slicing is mainly an issue with OOP, <code class="computeroutput"><span class="identifier">unregistered_type</span></code>
          exceptions are expected to be much less frequent with <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span></code>
          and <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span></code>. Contrived examples can
          be found, though:
        </p>
<pre class="programlisting"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span><span class="special">&lt;</span><span class="identifier">renderable</span><span class="special">&gt;</span> <span class="identifier">c1</span><span class="special">,</span><span class="identifier">c2</span><span class="special">;</span>
<span class="special">...</span> <span class="comment">// populate c2</span>

<span class="identifier">c1</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(*</span><span class="identifier">c2</span><span class="special">.</span><span class="identifier">begin</span><span class="special">());</span> <span class="comment">// throws: actual type of *c2.begin() not known by c1</span>
</pre>
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="poly_collection.tutorial.deeper_into_the_segmented_nature.segment_specific_interface"></a><a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.segment_specific_interface" title="Segment-specific interface">Segment-specific
        interface</a>
</h4></div></div></div>
<p>
          For most of the interface of a polymorphic collection, it is possible to
          only refer to the elements of a given segment by providing either their
          type or <code class="computeroutput"><span class="keyword">typeid</span><span class="special">()</span></code>.
          For instance:
        </p>
<pre class="programlisting"><span class="special">...</span> <span class="comment">// populate c with 8 assorted entities</span>

<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">size</span><span class="special">()&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>                    <span class="comment">// 8 sprites</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">size</span><span class="special">&lt;</span><span class="identifier">juggernaut</span><span class="special">&gt;()&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>        <span class="comment">// 2 juggernauts</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">size</span><span class="special">(</span><span class="keyword">typeid</span><span class="special">(</span><span class="identifier">juggernaut</span><span class="special">))&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>  <span class="comment">// alternate syntax</span>
<span class="identifier">c</span><span class="special">.</span><span class="identifier">clear</span><span class="special">&lt;</span><span class="identifier">juggernaut</span><span class="special">&gt;();</span>                        <span class="comment">// remove juggenauts only</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">empty</span><span class="special">&lt;</span><span class="identifier">juggernaut</span><span class="special">&gt;()&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>       <span class="comment">// 1 (no juggernauts left)</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">size</span><span class="special">()&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>                    <span class="comment">// 6 sprites remaining</span>
</pre>
<p>
          Note that any of these (except <a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.reserve" title="Reserve"><code class="computeroutput"><span class="identifier">reserve</span></code></a>) will throw <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">unregistered_type</span></code> if the type is not
          registered. Segment-specific addressability also includes traversal:
        </p>
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="poly_collection.tutorial.deeper_into_the_segmented_nature.local_iterators"></a><a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.local_iterators" title="Local iterators">Local
        iterators</a>
</h4></div></div></div>
<p>
          The following runs only over the <code class="computeroutput"><span class="identifier">warrior</span></code>s
          of the collection:
        </p>
<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span>
<span class="keyword">for</span><span class="special">(</span><span class="keyword">auto</span> <span class="identifier">first</span><span class="special">=</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(</span><span class="keyword">typeid</span><span class="special">(</span><span class="identifier">warrior</span><span class="special">)),</span><span class="identifier">last</span><span class="special">=</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span><span class="special">(</span><span class="keyword">typeid</span><span class="special">(</span><span class="identifier">warrior</span><span class="special">));</span>
    <span class="identifier">first</span><span class="special">!=</span><span class="identifier">last</span><span class="special">;++</span><span class="identifier">first</span><span class="special">){</span>
  <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
  <span class="identifier">first</span><span class="special">-&gt;</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span>
  <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
<span class="special">}</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
</pre>
<p>
          Output:
        </p>
<pre class="programlisting">warrior 2,warrior 6
</pre>
<p>
          <code class="computeroutput"><span class="identifier">begin</span><span class="special">|</span><span class="identifier">end</span><span class="special">(</span><span class="keyword">typeid</span><span class="special">(</span><span class="identifier">T</span><span class="special">))</span></code> return
          objects of type <code class="computeroutput"><span class="identifier">local_base_iterator</span></code>
          associated to the segment for <code class="computeroutput"><span class="identifier">T</span></code>.
          These iterators dereference to the same value as regular iterators (in
          the case of <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span><span class="special">&lt;</span><span class="identifier">base</span><span class="special">&gt;</span></code>,
          <code class="computeroutput"><span class="identifier">base</span><span class="special">&amp;</span></code>)
          but can only be used to traverse a given segment (for instance, <code class="computeroutput"><span class="identifier">local_base_iterator</span></code>'s from different
          segments cannot be compared between them). In exchange, <code class="computeroutput"><span class="identifier">local_base_iterator</span></code>
          is a <a href="http://en.cppreference.com/w/cpp/named_req/RandomAccessIterator" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">RandomAccessIterator</span></code></strong></span></a>,
          whereas whole-collection iterators only model <a href="http://en.cppreference.com/w/cpp/named_req/ForwardIterator" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">ForwardIterator</span></code></strong></span></a>.
        </p>
<p>
          A terser range-based <code class="computeroutput"><span class="keyword">for</span></code> loop
          can be used with the convenience <code class="computeroutput"><span class="identifier">segment</span></code>
          member function:
        </p>
<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span>
<span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&amp;</span> <span class="identifier">x</span><span class="special">:</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">segment</span><span class="special">(</span><span class="keyword">typeid</span><span class="special">(</span><span class="identifier">warrior</span><span class="special">))){</span>
  <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
  <span class="identifier">x</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span>
  <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
<span class="special">}</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
</pre>
<p>
          Even more powerful than <code class="computeroutput"><span class="identifier">local_base_iterator</span></code>
          is <code class="computeroutput"><span class="identifier">local_iterator</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span></code>:
        </p>
<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span>
<span class="keyword">for</span><span class="special">(</span><span class="keyword">auto</span> <span class="identifier">first</span><span class="special">=</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">&gt;(),</span><span class="identifier">last</span><span class="special">=</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">&gt;();</span>
    <span class="identifier">first</span><span class="special">!=</span><span class="identifier">last</span><span class="special">;++</span><span class="identifier">first</span><span class="special">){</span>
  <span class="identifier">first</span><span class="special">-&gt;</span><span class="identifier">rank</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="number">0</span><span class="special">,</span><span class="string">"super"</span><span class="special">);</span>
  <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
  <span class="identifier">first</span><span class="special">-&gt;</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span>
  <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
<span class="special">}</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>

<span class="comment">// range-based for loop alternative</span>

<span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span>
<span class="keyword">for</span><span class="special">(</span><span class="keyword">auto</span><span class="special">&amp;</span> <span class="identifier">x</span><span class="special">:</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">segment</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">&gt;()){</span>
  <span class="identifier">x</span><span class="special">.</span><span class="identifier">rank</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="number">0</span><span class="special">,</span><span class="string">"super"</span><span class="special">);</span>
  <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
  <span class="identifier">x</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span>
  <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
<span class="special">}</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
</pre>
<p>
          This appends a <code class="computeroutput"><span class="string">"super"</span></code>
          prefix to the <code class="computeroutput"><span class="identifier">rank</span></code> data
          member of existing warriors:
        </p>
<pre class="programlisting">superwarrior 2,superwarrior 6
</pre>
<p>
          The observant reader will have noticed that in order to access <code class="computeroutput"><span class="identifier">rank</span></code>, which is a member of <code class="computeroutput"><span class="identifier">warrior</span></code> rather than its base class <code class="computeroutput"><span class="identifier">sprite</span></code>, <code class="computeroutput"><span class="identifier">first</span></code>
          (or <code class="computeroutput"><span class="identifier">x</span></code> in the range <code class="computeroutput"><span class="keyword">for</span></code> loop version) has to refer to a <code class="computeroutput"><span class="identifier">warrior</span><span class="special">&amp;</span></code>,
          and this is precisely the difference between <code class="computeroutput"><span class="identifier">local_iterator</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">&gt;</span></code> (the type returned by <code class="computeroutput"><span class="identifier">begin</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">&gt;()</span></code>)
          and <code class="computeroutput"><span class="identifier">local_base_iterator</span></code>.
          <code class="computeroutput"><span class="identifier">local_iterator</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">&gt;</span></code>
          is also a <a href="http://en.cppreference.com/w/cpp/named_req/RandomAccessIterator" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">RandomAccessIterator</span></code></strong></span></a>:
          for most respects, [<code class="computeroutput"><span class="identifier">begin</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;()</span></code>, <code class="computeroutput"><span class="identifier">end</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;()</span></code>) can be regarded as a range over
          an array of <code class="computeroutput"><span class="identifier">T</span></code> objects.
          <code class="computeroutput"><span class="identifier">local_iterator</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span></code>s
          can be explicitly converted to <code class="computeroutput"><span class="identifier">local_base_iterator</span></code>s.
          Conversely, if a <code class="computeroutput"><span class="identifier">local_base_iterator</span></code>
          is associated to a segment for <code class="computeroutput"><span class="identifier">T</span></code>,
          it can then be explictly converted to a <code class="computeroutput"><span class="identifier">local_iterator</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span></code> (otherwise the conversion is undefined
          behavior).
        </p>
<p>
          The figure shows the action scopes of all the iterators associated to a
          polymorphic collection (<code class="computeroutput"><span class="identifier">const_</span></code>
          versions not included):
        </p>
<p>
          <span class="inlinemediaobject"><img src="img/poly_collection_iterators.png"></span>
        </p>
<p>
          We have yet to describe the bottom part of the diagram. Whereas <code class="computeroutput"><span class="identifier">segment</span><span class="special">(</span><span class="keyword">typeid</span><span class="special">(</span><span class="identifier">T</span><span class="special">))</span></code> is
          used to range over the <span class="emphasis"><em>elements</em></span> of a particular segment,
          <code class="computeroutput"><span class="identifier">segment_traversal</span><span class="special">()</span></code>
          returns an object for ranging over <span class="emphasis"><em>segments</em></span>, so that
          the whole collection can be processed with a nested segment-element <code class="computeroutput"><span class="keyword">for</span></code> loop like the following:
        </p>
<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span>
<span class="keyword">for</span><span class="special">(</span><span class="keyword">auto</span> <span class="identifier">seg</span><span class="special">:</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">segment_traversal</span><span class="special">()){</span>
  <span class="keyword">for</span><span class="special">(</span><span class="identifier">sprite</span><span class="special">&amp;</span> <span class="identifier">s</span><span class="special">:</span><span class="identifier">seg</span><span class="special">){</span>
    <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
    <span class="identifier">s</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span>
    <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
  <span class="special">}</span>
<span class="special">}</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
</pre>
<p>
          Segment decomposition of traversal loops forms the basis of <a class="link" href="tutorial.html#poly_collection.tutorial.algorithms" title="Algorithms">improved-performance
          algorithms</a>.
        </p>
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="poly_collection.tutorial.deeper_into_the_segmented_nature.reserve"></a><a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.reserve" title="Reserve">Reserve</a>
</h4></div></div></div>
<p>
          Much like <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span></code>, segments can be made to reserve
          memory in advance to minimize reallocations:
        </p>
<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">reserve</span><span class="special">&lt;</span><span class="identifier">goblin</span><span class="special">&gt;(</span><span class="number">100</span><span class="special">);</span> <span class="comment">// no reallocation till we exceed 100 goblins</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">capacity</span><span class="special">&lt;</span><span class="identifier">goblin</span><span class="special">&gt;()&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span> <span class="comment">// prints 100</span>
</pre>
<p>
          If there is no segment for the indicated type (here, <code class="computeroutput"><span class="identifier">goblin</span></code>),
          one is automatically created. This is in contrast with the rest of segment-specific
          member functions, which throw <a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration" title="Type registration"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">unregistered_type</span></code></a>.
        </p>
<p>
          <code class="computeroutput"><span class="identifier">reserve</span></code> can deal with all
          segments at once. The following
        </p>
<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">reserve</span><span class="special">(</span><span class="number">1000</span><span class="special">);</span> <span class="comment">// reserve(1000) for each segment</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">capacity</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">&gt;()&lt;&lt;</span><span class="string">", "</span>
         <span class="special">&lt;&lt;</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">capacity</span><span class="special">&lt;</span><span class="identifier">juggernaut</span><span class="special">&gt;()&lt;&lt;</span><span class="string">", "</span>
         <span class="special">&lt;&lt;</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">capacity</span><span class="special">&lt;</span><span class="identifier">goblin</span><span class="special">&gt;()&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span> <span class="comment">// prints 1000, 1000, 1000</span>
</pre>
<p>
          instructs every <span class="emphasis"><em>existing</em></span> segment to reserve 1,000
          elements. If a segment is created later (through element insertion or with
          <a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration" title="Type registration">type
          registration</a>), its capacity will be different.
        </p>
<div class="note"><table border="0" summary="Note">
<tr>
<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../doc/src/images/note.png"></td>
<th align="left">Note</th>
</tr>
<tr><td align="left" valign="top"><p>
            Unlike standard containers, collection-level <code class="computeroutput"><span class="identifier">capacity</span><span class="special">()</span></code> and <code class="computeroutput"><span class="identifier">max_size</span><span class="special">()</span></code> are not provided because their usual
            semantics cannot be applied to Boost.PolyCollection: for instance, <code class="computeroutput"><span class="identifier">capacity</span><span class="special">()</span></code>
            is typically used to check how many elements can be inserted without
            reallocation, but in a segmented structure that depends on the exact
            types of the elements and whether they are registered or not.
          </p></td></tr>
</table></div>
</div>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="poly_collection.tutorial.insertion_and_emplacement"></a><a class="link" href="tutorial.html#poly_collection.tutorial.insertion_and_emplacement" title="Insertion and emplacement">Insertion
      and emplacement</a>
</h3></div></div></div>
<p>
        (Code samples from <a href="../../../libs/poly_collection/example/insertion_emplacement.cpp" target="_top"><code class="computeroutput"><span class="identifier">insertion_emplacement</span><span class="special">.</span><span class="identifier">cpp</span></code></a>.)
      </p>
<p>
        We already know that <code class="computeroutput"><span class="identifier">insert</span><span class="special">(</span><span class="identifier">x</span><span class="special">)</span></code>,
        without further positional information, stores <code class="computeroutput"><span class="identifier">x</span></code>
        at the end of its associated segment. When a regular iterator <code class="computeroutput"><span class="identifier">it</span></code> is provided, insertion happens at the
        position indicated if both <code class="computeroutput"><span class="identifier">it</span></code>
        and <code class="computeroutput"><span class="identifier">x</span></code> belong in the same
        segment; otherwise, <code class="computeroutput"><span class="identifier">it</span></code> is
        ignored. For instance, if our sprite collection has the following entities:
      </p>
<pre class="programlisting">juggernaut 0,juggernaut 4,juggernaut 7,goblin 1,goblin 3,goblin 5,warrior 2,warrior 6
</pre>
<p>
        then this code:
      </p>
<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">juggernaut</span><span class="special">{</span><span class="number">8</span><span class="special">});</span>
</pre>
<p>
        puts the new <code class="computeroutput"><span class="identifier">juggernaut</span></code> at
        the beginning:
      </p>
<pre class="programlisting"><span class="red">juggernaut 8</span>,juggernaut 0,juggernaut 4,juggernaut 7,goblin 1,...
</pre>
<p>
        whereas the position hint at
      </p>
<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">goblin</span><span class="special">{</span><span class="number">9</span><span class="special">});</span>
</pre>
<p>
        is ignored and the new <code class="computeroutput"><span class="identifier">goblin</span></code>
        gets inserted at the end of its segment:
      </p>
<pre class="programlisting">juggernaut 8,...,juggernaut 7,goblin 1,goblin 3,goblin 5,<span class="red">goblin 9</span>,warrior 2,...
</pre>
<p>
        <a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.local_iterators" title="Local iterators">Local
        iterators</a> can also be used to indicate the insertion position:
      </p>
<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">&lt;</span><span class="identifier">juggernaut</span><span class="special">&gt;()+</span><span class="number">2</span><span class="special">,</span><span class="identifier">juggernaut</span><span class="special">{</span><span class="number">10</span><span class="special">});</span>
                           <span class="comment">// ^^ remember local iterators are random access</span>
</pre>
<pre class="programlisting">juggernaut 8,juggernaut 0,<span class="red">juggernaut 10</span>,juggernaut 4,juggernaut 7,goblin 1,...
</pre>
<p>
        There is a caveat, though: when using a local iterator, the element inserted
        <span class="emphasis"><em>must belong to the indicated segment</em></span>:
      </p>
<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(</span><span class="keyword">typeid</span><span class="special">(</span><span class="identifier">warrior</span><span class="special">)),</span><span class="identifier">juggernaut</span><span class="special">{</span><span class="number">11</span><span class="special">});</span> <span class="comment">// undefined behavior!!</span>
</pre>
<p>
        Member functions are provided for range insertion, with and without a position
        hint:
      </p>
<pre class="programlisting"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span><span class="special">&lt;</span><span class="identifier">sprite</span><span class="special">&gt;</span> <span class="identifier">c2</span><span class="special">;</span>

<span class="identifier">c2</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span> <span class="comment">// read below</span>

<span class="comment">// add some more warriors</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">array</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">,</span><span class="number">3</span><span class="special">&gt;</span> <span class="identifier">aw</span><span class="special">={{</span><span class="number">11</span><span class="special">,</span><span class="number">12</span><span class="special">,</span><span class="number">13</span><span class="special">}};</span>
<span class="identifier">c2</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">aw</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">aw</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span>

<span class="comment">// add some goblins at the beginning of their segment</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">array</span><span class="special">&lt;</span><span class="identifier">goblin</span><span class="special">,</span><span class="number">3</span><span class="special">&gt;</span> <span class="identifier">ag</span><span class="special">={{</span><span class="number">14</span><span class="special">,</span><span class="number">15</span><span class="special">,</span><span class="number">16</span><span class="special">}};</span>
<span class="identifier">c2</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">c2</span><span class="special">.</span><span class="identifier">begin</span><span class="special">&lt;</span><span class="identifier">goblin</span><span class="special">&gt;(),</span><span class="identifier">ag</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">ag</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span>
</pre>
<p>
        As <a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration" title="Type registration">already
        explained</a>, care must be taken that types be pre-registered into the
        collection if they are not passed as references to their actual type. So,
        why did not this line
      </p>
<pre class="programlisting"><span class="identifier">c2</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span>
</pre>
<p>
        throw <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">unregistered_type</span></code>? As it happens, in the
        special case where the inserted range belongs to a polymorphic collection
        of the same type, registration is done automatically <a href="#ftn.poly_collection.tutorial.insertion_and_emplacement.f0" class="footnote" name="poly_collection.tutorial.insertion_and_emplacement.f0"><sup class="footnote">[16]</sup></a>.
      </p>
<p>
        <a name="poly_collection.tutorial.insertion_and_emplacement.emplacement"></a>Emplacement
        is slightly different for Boost.PolyCollection than with standard containers.
        Consider this attempt at emplacing a <code class="computeroutput"><span class="identifier">goblin</span></code>:
      </p>
<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">emplace</span><span class="special">(</span><span class="number">11</span><span class="special">);</span> <span class="comment">// does not compile</span>
</pre>
<p>
        If examined carefully, it is only natural that the code above not compile:
        Boost.PolyCollection cannot possibly know that it is precisely a <code class="computeroutput"><span class="identifier">goblin</span></code> that we want to emplace and not
        some other type constructible from an <code class="computeroutput"><span class="keyword">int</span></code>
        (like <code class="computeroutput"><span class="identifier">warrior</span></code>, <code class="computeroutput"><span class="identifier">juggernaut</span></code> or an unrelated class). So,
        the type of the emplaced element has to be specified explicitly:
      </p>
<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">emplace</span><span class="special">&lt;</span><span class="identifier">goblin</span><span class="special">&gt;(</span><span class="number">11</span><span class="special">);</span> <span class="comment">// now it works</span>
</pre>
<p>
        As with <code class="computeroutput"><span class="identifier">insert</span></code>, a position
        can be indicated for emplacing:
      </p>
<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">emplace_hint</span><span class="special">&lt;</span><span class="identifier">juggernaut</span><span class="special">&gt;(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="number">12</span><span class="special">);</span> <span class="comment">// at the beginning if possible</span>
<span class="identifier">c</span><span class="special">.</span><span class="identifier">emplace_pos</span><span class="special">&lt;</span><span class="identifier">goblin</span><span class="special">&gt;(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">&lt;</span><span class="identifier">goblin</span><span class="special">&gt;()+</span><span class="number">2</span><span class="special">,</span><span class="number">13</span><span class="special">);</span> <span class="comment">// amidst the goblins</span>
<span class="identifier">c</span><span class="special">.</span><span class="identifier">emplace_pos</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">&gt;(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(</span><span class="keyword">typeid</span><span class="special">(</span><span class="identifier">warrior</span><span class="special">)),</span><span class="number">14</span><span class="special">);</span> <span class="comment">// local_base_iterator</span>
</pre>
<p>
        Note the naming here: <code class="computeroutput"><span class="identifier">emplace_hint</span></code>
        is used when the position is indicated with a regular iterator, and for local
        iterators it is <code class="computeroutput"><span class="identifier">emplace_pos</span></code>.
      </p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="poly_collection.tutorial.exceptions"></a><a class="link" href="tutorial.html#poly_collection.tutorial.exceptions" title="Exceptions">Exceptions</a>
</h3></div></div></div>
<p>
        (Code samples from <a href="../../../libs/poly_collection/example/exceptions.cpp" target="_top"><code class="computeroutput"><span class="identifier">exceptions</span><span class="special">.</span><span class="identifier">cpp</span></code></a>.)
      </p>
<p>
        Besides the usual exceptions like <a href="http://en.cppreference.com/w/cpp/memory/new/bad_alloc" target="_top"><code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">bad_alloc</span></code></a>
        and those generated by user-provided types, polymorphic collections can throw
        the following:
      </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
            <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">unregistered_type</span></code>
          </li>
<li class="listitem">
            <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">not_copy_constructible</span></code>
          </li>
<li class="listitem">
            <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">not_equality_comparable</span></code>
          </li>
</ul></div>
<p>
        The situations in which the first is raised have been <a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration" title="Type registration">already
        discussed</a>; let us focus on the other two.
      </p>
<p>
        We have a new type of sprite in our game defined by the non-copyable class
        <code class="computeroutput"><span class="identifier">elf</span></code>:
      </p>
<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">elf</span><span class="special">:</span><span class="identifier">sprite</span>
<span class="special">{</span>
  <span class="keyword">using</span> <span class="identifier">sprite</span><span class="special">::</span><span class="identifier">sprite</span><span class="special">;</span>
  <span class="identifier">elf</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">elf</span><span class="special">&amp;)=</span><span class="keyword">delete</span><span class="special">;</span> <span class="comment">// not copyable</span>
  <span class="identifier">elf</span><span class="special">(</span><span class="identifier">elf</span><span class="special">&amp;&amp;)=</span><span class="keyword">default</span><span class="special">;</span>     <span class="comment">// but moveable</span>
  <span class="keyword">void</span> <span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="identifier">os</span><span class="special">)</span><span class="keyword">const</span> <span class="identifier">override</span><span class="special">{</span><span class="identifier">os</span><span class="special">&lt;&lt;</span><span class="string">"elf "</span><span class="special">&lt;&lt;</span><span class="identifier">id</span><span class="special">;}</span>
<span class="special">};</span>
</pre>
<p>
        and we use it without problems until we write this:
      </p>
<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">elf</span><span class="special">{</span><span class="number">0</span><span class="special">});</span> <span class="comment">// no problem</span>
<span class="special">...</span>

<span class="identifier">c2</span><span class="special">=</span><span class="identifier">c</span><span class="special">;</span> <span class="comment">// throws boost::poly_collection::not_copy_constructible</span>
</pre>
<p>
        The first insertion works because the <code class="computeroutput"><span class="identifier">elf</span></code>
        object passed is <span class="emphasis"><em>temporary</em></span> and can be <span class="emphasis"><em>moved</em></span>
        into the container, but the second statement actually needs to <span class="emphasis"><em>copy</em></span>
        the <code class="computeroutput"><span class="identifier">elf</span></code> elements in <code class="computeroutput"><span class="identifier">c</span></code> to <code class="computeroutput"><span class="identifier">c2</span></code>,
        hence the exception.
      </p>
<p>
        The potentially surprising aspect of this behavior is that standard containers
        signal this kind of problems by <span class="emphasis"><em>failing at compile time</em></span>.
        Here we cannot afford this luxury because the exact types contained in a
        polymorphic collection are not known until run time (for instance, if <code class="computeroutput"><span class="identifier">elf</span></code> elements had been erased before copying
        <code class="computeroutput"><span class="identifier">c</span></code> to <code class="computeroutput"><span class="identifier">c2</span></code>
        everything would have worked): basically, the deferral of errors from compile
        time to run time is an intrinsic feature of dynamic polymorphism.
      </p>
<p>
        In the same vein, equality comparison requires that elements themselves be
        equality comparable:
      </p>
<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">clear</span><span class="special">&lt;</span><span class="identifier">elf</span><span class="special">&gt;();</span> <span class="comment">// get rid of non-copyable elfs</span>
<span class="identifier">c2</span><span class="special">=</span><span class="identifier">c</span><span class="special">;</span>           <span class="comment">// now it works</span>
<span class="comment">// check that the two are indeed equal</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;(</span><span class="identifier">c</span><span class="special">==</span><span class="identifier">c2</span><span class="special">)&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
                <span class="comment">// throws boost::poly_collection::not_equality_comparable</span>
</pre>
<p>
        The above is unremarkable once we notice we have not defined <code class="computeroutput"><span class="keyword">operator</span><span class="special">==</span></code>
        for any <code class="computeroutput"><span class="identifier">sprite</span></code>. The problem
        may go unnoticed for quite some time, however, because determining that two
        polymorphic collections are equal (i.e. all their non-empty segments are
        equal) can return <code class="computeroutput"><span class="keyword">false</span></code> without
        comparing anything at all (for instance, if segment sizes differ), in which
        case no exception is thrown.
      </p>
<div class="note"><table border="0" summary="Note">
<tr>
<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../doc/src/images/note.png"></td>
<th align="left">Note</th>
</tr>
<tr><td align="left" valign="top"><p>
          Operators for <code class="computeroutput"><span class="special">&lt;</span></code>, <code class="computeroutput"><span class="special">&lt;=</span></code>, <code class="computeroutput"><span class="special">&gt;</span></code>
          and <code class="computeroutput"><span class="special">&gt;=</span></code> comparison are not
          provided because <span class="emphasis"><em>segment</em></span> order is not fixed and may
          vary across otherwise identical collections. The situation is similar to
          that of standard <a href="http://en.cppreference.com/w/cpp/named_req/UnorderedAssociativeContainer" target="_top">unordered
          associative containers.</a>
        </p></td></tr>
</table></div>
<p>
        These three are all the intrinsic exceptions thrown by Boost.PolyCollection.
        The implication is that if a type is <a href="http://en.cppreference.com/w/cpp/named_req/CopyConstructible" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">CopyConstructible</span></code></strong></span></a>,
        <a href="http://en.cppreference.com/w/cpp/named_req/MoveAssignable" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">MoveAssignable</span></code></strong></span></a>
        (or move construction does not throw) and <a href="http://en.cppreference.com/w/cpp/named_req/EqualityComparable" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">EqualityComparable</span></code></strong></span></a>,
        then the entire interface of Boost.PolyCollection is unrestrictedly available
        for it <a href="#ftn.poly_collection.tutorial.exceptions.f0" class="footnote" name="poly_collection.tutorial.exceptions.f0"><sup class="footnote">[17]</sup></a>.
      </p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="poly_collection.tutorial.algorithms"></a><a class="link" href="tutorial.html#poly_collection.tutorial.algorithms" title="Algorithms">Algorithms</a>
</h3></div></div></div>
<div class="toc"><dl class="toc"><dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.algorithms.type_restitution">Type
        restitution</a></span></dt></dl></div>
<p>
        (Code samples from <a href="../../../libs/poly_collection/example/algorithms.cpp" target="_top"><code class="computeroutput"><span class="identifier">algorithms</span><span class="special">.</span><span class="identifier">cpp</span></code></a>. C++14 generic lambda expressions
        are used.)
      </p>
<p>
        The ultimate purpose of Boost.PolyCollection is to speed up the processing
        of large quantities of polymorphic entities, in particular for those operations
        that involve linear traversal as implemented with a <code class="computeroutput"><span class="keyword">for</span></code>-loop
        or using the quintessential <a href="http://en.cppreference.com/w/cpp/algorithm/for_each" target="_top"><code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">for_each</span></code></a>
        algorithm.
      </p>
<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">for_each</span><span class="special">(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),[&amp;](</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&amp;</span> <span class="identifier">s</span><span class="special">){</span>
  <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
  <span class="identifier">s</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span>
  <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
<span class="special">});</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
</pre>
<p>
        Replacing the container used in the program from classic alternatives to
        Boost.PolyCollection:
      </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
            <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">base</span><span class="special">*&gt;</span></code>
            (or similar) → <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span><span class="special">&lt;</span><span class="identifier">base</span><span class="special">&gt;</span></code>
          </li>
<li class="listitem">
            <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">function</span><span class="special">&lt;</span><span class="identifier">signature</span><span class="special">&gt;&gt;</span></code>
            → <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span><span class="special">&lt;</span><span class="identifier">signature</span><span class="special">&gt;</span></code>
          </li>
<li class="listitem">
            <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">any</span><span class="special">&lt;</span><span class="identifier">concept_</span><span class="special">&gt;&gt;</span></code>
            → <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span><span class="special">&lt;</span><span class="identifier">concept_</span><span class="special">&gt;</span></code>
          </li>
</ul></div>
<p>
        is expected to increase performance due to better caching and branch prediction
        behavior. But there is still room for improvement.
      </p>
<p>
        Consider this transformation of the code above using a double segment-element
        loop (based on the <a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.local_iterators" title="Local iterators">local
        iterator</a> capabilities of Boost.PolyCollection):
      </p>
<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span>
<span class="keyword">for</span><span class="special">(</span><span class="keyword">auto</span> <span class="identifier">seg_info</span><span class="special">:</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">segment_traversal</span><span class="special">()){</span>
  <span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&amp;</span> <span class="identifier">s</span><span class="special">:</span><span class="identifier">seg_info</span><span class="special">){</span>
    <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
    <span class="identifier">s</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span>
    <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
  <span class="special">}</span>
<span class="special">}</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
</pre>
<p>
        Although not obvious at first sight, this version of the same basic operation
        is actually <span class="emphasis"><em>faster</em></span> than the first one: for a segmented
        structure such as used by Boost.PolyCollection, each iteration with the non-local
        iterator passed to <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">for_each</span></code> involves:
      </p>
<div class="orderedlist"><ol class="orderedlist" type="1">
<li class="listitem">
            hopping to next position in the segment,
          </li>
<li class="listitem">
            checking for <span class="emphasis"><em>end of segment</em></span> (always),
          </li>
<li class="listitem">
            if at end (infrequent), selecting the next segment,
          </li>
<li class="listitem">
            checking for <span class="emphasis"><em>end of range</em></span> (always),
          </li>
</ol></div>
<p>
        whereas in the second version, iteration on the inner loop, where most processing
        happens, is a simple increment-and-check operation, that is, there is one
        less check (which happens at the much shorter outer loop). When the workload
        of the algorithm (the actually useful stuff done with the elements themselves)
        is relatively light, the overhead of looping can be very significant.
      </p>
<p>
        To make it easier for the user to take advantage of faster segment-element
        looping, Boost.PolyCollection provides its own version of <code class="computeroutput"><span class="identifier">for_each</span></code>
        based on that technique:
      </p>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">poly_collection</span><span class="special">/</span><span class="identifier">algorithm</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
<span class="special">...</span>

<span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span>
<span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">for_each</span><span class="special">(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),[&amp;](</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&amp;</span> <span class="identifier">s</span><span class="special">){</span>
  <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
  <span class="identifier">s</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span>
  <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
<span class="special">});</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
</pre>
<p>
        <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">for_each</span></code> has the same interface and behavior
        as <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">for_each</span></code> except for the fact that it only
        works for (non-local) iterators of a polymorphic container <a href="#ftn.poly_collection.tutorial.algorithms.f0" class="footnote" name="poly_collection.tutorial.algorithms.f0"><sup class="footnote">[18]</sup></a>. Versions of other standard algorithms are provided as well:
      </p>
<pre class="programlisting"><span class="keyword">auto</span> <span class="identifier">n</span><span class="special">=</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">count_if</span><span class="special">(</span>
  <span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),[](</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&amp;</span> <span class="identifier">s</span><span class="special">){</span><span class="keyword">return</span> <span class="identifier">s</span><span class="special">.</span><span class="identifier">id</span><span class="special">%</span><span class="number">2</span><span class="special">==</span><span class="number">0</span><span class="special">;});</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">n</span><span class="special">&lt;&lt;</span><span class="string">" sprites with even id\n"</span><span class="special">;</span>
</pre>
<p>
        In fact, variants are given of most (though not all) of the algorithms in
        <a href="http://en.cppreference.com/w/cpp/algorithm" target="_top"><code class="computeroutput"><span class="special">&lt;</span><span class="identifier">algorithm</span><span class="special">&gt;</span></code></a>
        among those that are compatible with polymorphic collections <a href="#ftn.poly_collection.tutorial.algorithms.f1" class="footnote" name="poly_collection.tutorial.algorithms.f1"><sup class="footnote">[19]</sup></a>. Check the <a class="link" href="reference.html#poly_collection.reference.header_boost_poly_collection_alg" title='Header "boost/poly_collection/algorithm.hpp" synopsis'>reference</a>
        for details.
      </p>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="poly_collection.tutorial.algorithms.type_restitution"></a><a class="link" href="tutorial.html#poly_collection.tutorial.algorithms.type_restitution" title="Type restitution">Type
        restitution</a>
</h4></div></div></div>
<p>
          By <span class="emphasis"><em>type restitution</em></span> we mean the generic process of
          getting a concrete entity from an abstract one by providing missing type
          information:
        </p>
<pre class="programlisting"><span class="identifier">sprite</span><span class="special">*</span>  <span class="identifier">ps</span><span class="special">=</span><span class="keyword">new</span> <span class="identifier">warrior</span><span class="special">{</span><span class="number">5</span><span class="special">};</span>
<span class="comment">// sprite -&gt; warrior</span>
<span class="identifier">warrior</span><span class="special">*</span> <span class="identifier">pw</span><span class="special">=</span><span class="keyword">static_cast</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">*&gt;(</span><span class="identifier">ps</span><span class="special">);</span>

<span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">any</span><span class="special">&lt;</span><span class="identifier">renderable</span><span class="special">&gt;</span> <span class="identifier">r</span><span class="special">=</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">{</span><span class="string">"hello"</span><span class="special">};</span>
<span class="comment">// renderable -&gt; std::string</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">&amp;</span> <span class="identifier">str</span><span class="special">=</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">any_cast</span><span class="special">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">&amp;&gt;(</span><span class="identifier">r</span><span class="special">);</span>
</pre>
<p>
          Type restitution has the potential to increase performance. Consider for
          instance the following:
        </p>
<pre class="programlisting"><span class="comment">// render r with std::string restitution</span>
<span class="keyword">if</span><span class="special">(</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">typeid_of</span><span class="special">(</span><span class="identifier">r</span><span class="special">)==</span><span class="keyword">typeid</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">)){</span>
  <span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">&amp;</span> <span class="identifier">str</span><span class="special">=</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">any_cast</span><span class="special">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">&amp;&gt;(</span><span class="identifier">r</span><span class="special">);</span>
  <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">str</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
<span class="special">}</span>
<span class="keyword">else</span><span class="special">{</span>
  <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">r</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
<span class="special">}</span>
</pre>
<p>
          Behaviorwise this code is equivalent to simply executing <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">r</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span></code>, but when type restitution
          succeeds the statement <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">str</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span></code>
          is skipping a virtual-like call that would have happened if <code class="computeroutput"><span class="identifier">r</span></code> were used instead. From a general point
          of view, supplying the compiler with extra type information allows it to
          perform more optimizations than in the abstract case, inlining being the
          prime example.
        </p>
<p>
          All Boost.PolyCollection algorithms accept an optional list of types for
          restitution. Let us use the <a class="link" href="tutorial.html#poly_collection.tutorial.basics.boost_any_collection" title="boost::any_collection"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span></code></a> scenario to illustrate
          this point:
        </p>
<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span>
<span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">for_each</span>
  <span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">,</span><span class="identifier">juggernaut</span><span class="special">,</span><span class="identifier">goblin</span><span class="special">&gt;(</span> <span class="comment">// restituted types</span>
  <span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),[&amp;](</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&amp;</span> <span class="identifier">x</span><span class="special">){</span> <span class="comment">// loop traverses *all* elements</span>
    <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">&lt;&lt;</span><span class="identifier">x</span><span class="special">;</span>
    <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
  <span class="special">});</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
</pre>
<p>
          Output:
        </p>
<pre class="programlisting">warrior 2,warrior 6,[pop-up 1],[pop-up 2],juggernaut 0,juggernaut 4,
juggernaut 7,goblin 1,goblin 3,goblin 5,"stamina: 10,000","game over"
</pre>
<p>
          This rendering loop differs from the non-restituting one in two aspects:
        </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
              A list of types is provided as template arguments to the algorithm.
              This is an indication that the types <span class="emphasis"><em>may</em></span> be actually
              present in the collection, not a promise. Also, the list of types need
              not be exhaustive, that is, some unlisted types could be present in
              the collection —in the example above, the loop traverses <span class="bold"><strong>all</strong></span> elements (including <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span></code>s
              and <code class="computeroutput"><span class="identifier">window</span></code>s), not only
              those corresponding to restituted types. In general, the more types
              are restituted, the greater the potential improvement in performance.
            </li>
<li class="listitem">
              The lambda function passed is a generic one accepting its argument
              as <code class="computeroutput"><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&amp;</span></code> <a href="#ftn.poly_collection.tutorial.algorithms.type_restitution.f0" class="footnote" name="poly_collection.tutorial.algorithms.type_restitution.f0"><sup class="footnote">[20]</sup></a>.
            </li>
</ul></div>
<p>
          Internally, <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">for_each</span></code> checks for each segment if its
          type, say <code class="computeroutput"><span class="identifier">T</span></code>, belongs in
          the type restitution list: if this is the case, the lambda function is
          passed a <code class="computeroutput"><span class="keyword">const</span> <span class="identifier">T</span><span class="special">&amp;</span></code> rather than the generic <code class="computeroutput"><span class="keyword">const</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">&amp;</span></code>. For each restituted type we are saving
          indirection calls and possibly getting inlining optimizations, etc. As
          we see in the <a class="link" href="performance.html" title="Performance">performance section</a>,
          the speedup can be very significant.
        </p>
<p>
          Type restitution works equally for the rest of collections of Boost.PolyCollection.
          When using <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span></code>, though, the case of
          improved performance is more tricky:
        </p>
<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span>
<span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">for_each</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">,</span><span class="identifier">juggernaut</span><span class="special">,</span><span class="identifier">goblin</span><span class="special">&gt;(</span>
  <span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),[&amp;](</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&amp;</span> <span class="identifier">s</span><span class="special">){</span>
    <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
    <span class="identifier">s</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span>
    <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
  <span class="special">});</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
</pre>
<p>
          The problem here is that, even though the argument to the lambda function
          will be restituted (when appropriate) to <code class="computeroutput"><span class="identifier">warrior</span><span class="special">&amp;</span></code>, <code class="computeroutput"><span class="identifier">juggernaut</span><span class="special">&amp;</span></code> or <code class="computeroutput"><span class="identifier">goblin</span><span class="special">&amp;</span></code>, using it still involves doing a virtual
          function call in <code class="computeroutput"><span class="identifier">s</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">)</span></code>.
          Whether this call is resolved to a non-virtual one depends on the quality
          of implementation of the compiler:
        </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
              If the concrete class is marked as <a href="http://en.cppreference.com/w/cpp/language/final" target="_top"><code class="computeroutput"><span class="identifier">final</span></code></a>, the compiler <span class="emphasis"><em>in
              principle</em></span> has enough information to get rid of the virtual
              function call.
            </li>
<li class="listitem">
              Other than this, <a href="http://hubicka.blogspot.com.es/2014/01/devirtualization-in-c-part-1.html" target="_top"><span class="emphasis"><em>devirtualization</em></span></a>
              capabilities <span class="emphasis"><em>may</em></span> be able to figure out that the
              type restitution scenario is actually casting the element to its true
              type, in which case, again, virtual calls are not needed.
            </li>
</ul></div>
</div>
</div>
<div class="footnotes">
<br><hr style="width:100; text-align:left;margin-left: 0">
<div id="ftn.poly_collection.tutorial.basics.boost_function_collection.f0" class="footnote"><p><a href="#poly_collection.tutorial.basics.boost_function_collection.f0" class="para"><sup class="para">[12] </sup></a>
            Note that all <code class="computeroutput"><span class="identifier">sprite</span></code>s
            come into one segment: this is why goblins #1 and #3 are not adjacent.
            Exercise for the reader: change the code of the example so that sprites
            are further segmented according to their concrete type.
          </p></div>
<div id="ftn.poly_collection.tutorial.basics.boost_function_collection.f1" class="footnote"><p><a href="#poly_collection.tutorial.basics.boost_function_collection.f1" class="para"><sup class="para">[13] </sup></a>
            Except when small buffer optimization applies.
          </p></div>
<div id="ftn.poly_collection.tutorial.basics.boost_any_collection.f0" class="footnote"><p><a href="#poly_collection.tutorial.basics.boost_any_collection.f0" class="para"><sup class="para">[14] </sup></a>
            Actually, it is <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">any</span><span class="special">&lt;</span><span class="identifier">Concept2</span><span class="special">,</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">_self</span><span class="special">&amp;&gt;</span></code> for some internally defined
            <code class="computeroutput"><span class="identifier">Concept2</span></code> that extends
            <code class="computeroutput"><span class="identifier">Concept</span></code>.
          </p></div>
<div id="ftn.poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration.f0" class="footnote"><p><a href="#poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration.f0" class="para"><sup class="para">[15] </sup></a>
            If this is conceptually difficult to grasp, consider the potentially
            more obvious case where <code class="computeroutput"><span class="identifier">warrior</span></code>
            is defined in a dynamic module linked to the main program: the code of
            <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span></code>, which has been compiled
            before linking, cannot even know the size of this as-of-yet unseen class,
            so hardly can it allocate a segment for the received object.
          </p></div>
<div id="ftn.poly_collection.tutorial.insertion_and_emplacement.f0" class="footnote"><p><a href="#poly_collection.tutorial.insertion_and_emplacement.f0" class="para"><sup class="para">[16] </sup></a>
          That is, Boost.PolyCollection has enough static information to do type
          registration without further assistance from the user.
        </p></div>
<div id="ftn.poly_collection.tutorial.exceptions.f0" class="footnote"><p><a href="#poly_collection.tutorial.exceptions.f0" class="para"><sup class="para">[17] </sup></a>
          Provided, of course, that the type has the <span class="emphasis"><em>right</em></span> to
          be in the collection, that is, it is derived from the specified base, or
          callable with the specified signature, etc.
        </p></div>
<div id="ftn.poly_collection.tutorial.algorithms.f0" class="footnote"><p><a href="#poly_collection.tutorial.algorithms.f0" class="para"><sup class="para">[18] </sup></a>
          For any other type of iterator, it is guaranteed not to compile.
        </p></div>
<div id="ftn.poly_collection.tutorial.algorithms.f1" class="footnote"><p><a href="#poly_collection.tutorial.algorithms.f1" class="para"><sup class="para">[19] </sup></a>
          For example, algorithms requiring bidirectional iterators or a higher category
          are not provided because polymorphic collections have forward-only iterators.
        </p></div>
<div id="ftn.poly_collection.tutorial.algorithms.type_restitution.f0" class="footnote"><p><a href="#poly_collection.tutorial.algorithms.type_restitution.f0" class="para"><sup class="para">[20] </sup></a>
                This requires C++14, but the same effect can be achieved in C++11
                providing an equivalent, if more cumbersome, functor with a templatized
                call operator.
              </p></div>
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright © 2016-2021 Joaquín M López Muñoz<p>
        Distributed under the Boost Software License, Version 1.0. (See accompanying
        file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
      </p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="an_efficient_polymorphic_data_st.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../poly_collection.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="performance.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
